#include <bits/stdc++.h>

using namespace std;

/**********************************************
 *
 * 建模：
 * 使用数字大小表示 煎饼的大小，为了方便起见，
 * 当煎饼数为n时候，采用1~n表示煎饼的大小
 * 如此 pancakes 属于1~n的全排列
 *
 * ************************************************/

class Solution {
public:
    Solution(vector<int> &pancakes) {
        this->pancakes = pancakes;
        cnt = 0;
    }
    int SortPancakes() {
        for (int _size = pancakes.size(); _size > 0; _size--) {
            if (pancakes[_size - 1] == _size) continue; // 已经在所在位置了
            flip(search(_size)); // 翻转到头
            flip(_size - 1); // 翻转到尾
        }
        return cnt;
    }

    void print() {
        cout << "now, pancakes are ";
        for (const auto &p : pancakes) {
            cout << p << ' ';
        }
        cout << ", cnt of flip is " << cnt << endl;
    }
private:
    vector<int> pancakes;
    int cnt;
    void flip(int ed) {
        // 翻转范围为 [0,ed]

        if (ed == 0) return; // 长度为1 不要翻转

        cnt++; // 翻转次数+1
        int mid = (ed + 1) >> 1;
        for (int i = 0; i < mid; i++) swap(pancakes[i], pancakes[ed - i]);

    }

    int search(int target) {
        for (int i = 0; i < pancakes.size(); i++) {
            if (pancakes[i] == target)
                return i;
        }
        return -1;
    }


};


int main() {
    vector<int>pc{ 3,2,4,1 };
    Solution *s = new Solution(pc);
    s->print();
    s->SortPancakes();
    s->print();
    //system("pause");
    return 0;
}
